package ecc;

/**
 * Abstraction for the parametrization of elliptic curves over GF(p).<BR>
 * <BR>
 * @author  Paulo S. L. M. Barreto
 */

import java.io.InputStream;
import java.math.BigInteger;
import java.security.SecureRandom;

public class ECurve {

    /**
     * Convenient BigInteger constants
     */
    protected static final BigInteger
        _0 = BigInteger.valueOf(0L),
        _1 = BigInteger.valueOf(1L);

    /**
     * Rabin-Miller certainty used for primality testing
     */
    protected static final int PRIMALITY_CERTAINTY = 20;

    /**
     * Invalid parameters error message
     */
    public static final String invalidParams =
        "The specified parameters do not properly define a suitable elliptic curve";

    /**
     * Size of the underlying finite field GF(p)
     */
    public BigInteger p;

    /**
     * Coefficient of the elliptic curve equation
     */
    public BigInteger a;

    /**
     * Coefficient of the elliptic curve equation
     */
    public BigInteger b;

    /**
     * Cofactor of the base point (curve order u = h*n)
     */
    public BigInteger h;

    /**
     * Prime order of the base point (curve order u = h*n)
     */
    public BigInteger n;

    /**
     * The base point of large prime order n
     */
    public EPoint G;

    /**
     * The point at infinity
     */
    public EPoint infinity;

    /**
     * Multiples of the base point G by simple multiples of powers of 16.
     */
    protected EPoint[][] pp16G;

    /**
     * Create a full description of the elliptic curve over GF(p) satisfying
     * the equation y^2 = x^3 + ax + b with near-prime group order u = h*r
     * with a specified base point of prime order r.
     *
     * @param   p   an approximation for the size of the underlying finite field GF(p)
     *              (the actual value is taken to be the nearest odd prime not smaller than the given p or 3)
     * @param   a   curve equation coefficient
     * @param   b   curve equation coefficient
     * @param   h   cofactor of the curve group order
     * @param   n   prime order of the cryptographic subgroup
     * @param   Gx  x-coordinate of the base point of the curve
     * @param   Gy  y-coordinate of the base point of the curve
     *
     * @exception   IllegalArgumentException    if the selected parameters don't define a proper curve
     */
    private ECurve(BigInteger p, BigInteger a, BigInteger b, BigInteger h, BigInteger n, BigInteger Gx, BigInteger Gy) {
        if (!p.isProbablePrime(PRIMALITY_CERTAINTY)) {
            throw new IllegalArgumentException(invalidParams + ": " + "The underlying field size is not prime");
        }
        if (!n.isProbablePrime(PRIMALITY_CERTAINTY)) {
            throw new IllegalArgumentException(invalidParams + ": " + "The order of the base point is not prime");
        }
        this.p = p;
        infinity = new EPoint(this); // caveat: must be set *after* this.p
        this.a = a;
        this.b = b;
        this.h = h;
        this.n = n;
        this.G = new EPoint(this, Gx, Gy);

        if (!G.multiply(n).isZero()) {
            throw new IllegalArgumentException(invalidParams + ": " + "Wrong order");
        }

        pp16G = new EPoint[(n.bitLength() + 3)/4][16];
        EPoint[] pp16Gi = pp16G[0];
        //long elapsed = -System.currentTimeMillis();
        pp16Gi[0] = infinity;
        pp16Gi[1] = G;
        for (int i = 1, j = 2; i <= 7; i++, j += 2) {
            pp16Gi[j  ] = pp16Gi[i].twice(1);
            pp16Gi[j+1] = pp16Gi[j].add(G);
        }
        for (int i = 1; i < pp16G.length; i++) {
            EPoint[] pp16Gh = pp16Gi;
            pp16Gi = pp16G[i];
            pp16Gi[0] = pp16Gh[0];
            for (int j = 1; j < 16; j++) {
                pp16Gi[j] = pp16Gh[j].twice(4);
            }
        }
        //elapsed += System.currentTimeMillis();
        //System.out.println("*** Init16 time: " + (float)elapsed/1000 + " s.");
    }

    /**
     * Get a random nonzero point on this curve, given a fixed base point.
     *
     * @param   rand    a cryptographically strong PRNG
     *
     * @return  a random nonzero point on this curve
     */
    public EPoint pointFactory(SecureRandom rand) {
        BigInteger k;
        do {
            k = new BigInteger(p.bitLength(), rand).mod(p);
        } while (k.signum() == 0);
        return G.multiply(k);
    }

    /**
     * Check whether this curve contains a given point
     * (i.e. whether that point satisfies the curve equation)
     *
     * @param   P   the point whose pertinence or not to this curve is to be determined
     *
     * @return  true if this curve contains P, otherwise false
     */
    public boolean contains(EPoint P) {
        if (P.p.compareTo(p) != 0) {
            return false;
        }
        // check the projective equation y^2 = x^3 + a.x.z^4 + b.z^6,
        // i.e. x.x^2 + [a.x + b.z^2].(z^2)^2 - y^2 = 0
        // (the computation below never uses intermediate values larger than 3p^2)
        BigInteger
            x  = P.x,
            y  = P.y,
            z  = P.z,
            x2 = x.multiply(x).mod(p),
            z2 = z.multiply(z).mod(p),
            z4 = z2.multiply(z2).mod(p),
            br = a.multiply(x).add(b.multiply(z2)).mod(p); // bracketed expression [a.x + b.z^2]
        return x.multiply(x2).add(br.multiply(z4)).subtract(y.multiply(y)).mod(p).signum() == 0;
    }

    /**
     * Build a standard curve
     *
     * @param   fieldBits   underlying field size
     *
     * @return  the desired curve, or null if the specified field is nonstandard
     */
    public static ECurve getStandardCurve(int fieldBits) {
        switch (fieldBits) {
        case 160:
            return new ECurve(
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF", 16), // p
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC", 16), // a
                new BigInteger("1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45", 16),   // b
                _1, // h
                new BigInteger("0100000000000000000001F4C8F927AED3CA752257", 16), // n
                new BigInteger("4A96B5688EF573284664698968C38BB913CBFC82", 16),   // x
                new BigInteger("23A628553168947D59DCC912042351377AC5FB32", 16));  // y
        case 192:
            return new ECurve(
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", 16), // p
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC", 16), // a
                new BigInteger("64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1", 16),   // b
                _1, // h
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831", 16), // n
                new BigInteger("188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012", 16),   // x
                new BigInteger("07192B95FFC8DA78631011ED6B24CDD573F977A11E794811", 16));  // y
        case 224:
            return new ECurve(
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001", 16), // p
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE", 16), // a
                new BigInteger("00B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4", 16), // b
                _1, // h
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D", 16), // n
                new BigInteger("00B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21", 16), // x
                new BigInteger("00BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34", 16)); // y
        case 256:
            return new ECurve(
                new BigInteger("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", 16), // p
                new BigInteger("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC", 16), // a
                new BigInteger("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B", 16), // b
                _1, // h
                new BigInteger("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551", 16), // n
                new BigInteger("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296", 16), // x
                new BigInteger("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5", 16)); // y
        case 384:
            return new ECurve(
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF", 16), // p
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC", 16), // a
                new BigInteger("00B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF", 16), // b
                _1, // h
                new BigInteger("00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973", 16), // n
                new BigInteger("00AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7", 16), // x
                new BigInteger("3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F", 16));  // y
        case 521:
            return new ECurve(
                new BigInteger("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16), // p
                new BigInteger("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC", 16), // a
                new BigInteger("51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00", 16),   // b
                _1, // h
                new BigInteger("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409", 16), // n
                new BigInteger("00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66", 16), // x
                new BigInteger("011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650", 16)); // y
        default:
            return null;
        }
    }

    /**
     * Compute k*G
     *
     * @param   k   scalar by which the base point G is to be multiplied
     *
     * @return  k*G
     *
     * References:
     *
     * Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone,
     *      "Handbook of Applied Cryptography", CRC Press (1997),
     *      section 14.6 (Exponentiation)
     */
    /*
    public EPoint kG(BigInteger k) {
        k = k.mod(n); // reduce k mod n
        EPoint A = infinity;
        for (int i = 0, j = 0; i < pp16G.length; i++, j += 4) {
            int m = (k.testBit(j  ) ? 1 : 0) |
                    (k.testBit(j+1) ? 2 : 0) |
                    (k.testBit(j+2) ? 4 : 0) |
                    (k.testBit(j+3) ? 8 : 0);
            A = A.add(pp16G[i][m]);
        }
        return A;
    }
    //*/
    //*
    public EPoint kG(BigInteger k) {
        k = k.mod(n); // reduce k mod n
        EPoint A = infinity;
        for (int i = 0, w = 0; i < pp16G.length; i++, w >>>= 4) {
            if ((i & 7) == 0) {
                w = k.intValue();
                k = k.shiftRight(32);
            }
            A = A.add(pp16G[i][w & 0xf]);
        }
        return A;
    }
    //*/

    /**
     * Compute a square root of v (mod p) where p = 3 (mod 4).
     *
     * @return  a square root of v (mod p) if one exists, or null otherwise.
     *
     * @exception   IllegalArgumentException    if the size of the underlying finite field is not a prime p such that p mod 4 == 3.
     */
    BigInteger sqrt(BigInteger v) {
        if (!p.testBit(1)) {
            throw new IllegalArgumentException("This implementation is optimized for, and only works with, prime fields GF(p) where p = 3 (mod 4)");
        }
        /* Algorithm P1363 A.2.5 - Finding Square Roots Modulo a Prime */
        if (v.signum() == 0) {
            return _0;
        }
        BigInteger r = v.modPow(p.shiftRight(2).add(_1), p);
        // test solution:
        return r.multiply(r).subtract(v).mod(p).signum() == 0 ? r : null;
    }

}
